#include<iostream>
#include<vector>
#include<cstdlib>

using std::endl;
using std::cout;
void Swap(int& a,int& b)
{
	int t = a;
	a = b;
	b = t;
}
int GetRandomKey(const std::vector<int>& nums,int left, int right)
{
	return nums[rand() % (right - left + 1) + left];
}
void QuickSort(std::vector<int>& nums,int left,int right)
{
	//递归出口
	if(left >= right)
		return;
	
	int key = GetRandomKey(nums,left,right);
	int l = left - 1,r = right + 1,cur = left;
	
	while(cur < r)
	{
		if(nums[cur] == nums[key])
			cur++;
		else if(nums[cur] < nums[key]) 
			Swap(nums[cur++],nums[++l]);
		else 
			Swap(nums[cur],nums[--r]);
	}
	//排序左右区间
	QuickSort(nums,left,l);
	QuickSort(nums,r,right);
}

void Print(const std::vector<int>& arr)
{
	for(const auto&e:arr)
		cout<< e << " " ;
	cout<<endl;
}

int main()
{
	srand((unsigned int)time(nullptr));
	std::vector<int> arr = {0,2,3,1,4,6,5,7,8,9};
	Print(arr);
	QuickSort(arr,0,arr.size()-1);
	Print(arr);

	return 0;
}
